#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct Item {
    int price;    // 价格
    int value;    // 价格×重要度
};

Item master[100];  // 主件
vector<Item> accessories[100];  // 附件，每个主件可能有0-2个附件

int dp[100][32001]; // dp[i][j]表示考虑前i个主件（及其附件），总花费不超过j元的最大价值

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int v, p, q;
        cin >> v >> p >> q;
        
        if (q == 0) {  // 主件
            master[i].price = v;
            master[i].value = v * p;  // 价值 = 价格×重要度
        } else {  // 附件
            Item accessory;
            accessory.price = v;
            accessory.value = v * p;
            accessories[q].push_back(accessory);
        }
    }
    
    // 动态规划
    for (int i = 1; i <= m; i++) {
          for (int j = 0; j <= n; j++) {
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
        if (master[i].price == 0) continue;  // 跳过不是主件的物品
        
        // 逆序遍历避免重复选择
        for (int j = n; j >= master[i].price; j--) {
            // 不选主件i
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            
            // 选主件i
            dp[i][j] = max(dp[i][j], dp[i-1][j-master[i].price] + master[i].value);
            
            // 选主件i和附件1
            if (accessories[i].size() >= 1 && j >= master[i].price + accessories[i][0].price) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-master[i].price-accessories[i][0].price] + 
                               master[i].value + accessories[i][0].value);
            }
            
            // 选主件i和附件2
            if (accessories[i].size() >= 2 && j >= master[i].price + accessories[i][1].price) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-master[i].price-accessories[i][1].price] + 
                               master[i].value + accessories[i][1].value);
            }
            
            // 选主件i和附件1、2
            if (accessories[i].size() >= 2 && j >= master[i].price + accessories[i][0].price + accessories[i][1].price) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-master[i].price-accessories[i][0].price-accessories[i][1].price] + 
                               master[i].value + accessories[i][0].value + accessories[i][1].value);
            }
        }
        
        // 复制状态到下一个主件
      
    }
    
    cout << dp[m][n] << endl;
    return 0;
}